class Node:
    def __init__(self, key, val):
        self.val = val
        self.key = key
        self.prev = None
        self.next = None


class LRUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.head = Node(None, None)
        self.tail = Node(None, None)
        self.head.next = self.tail
        self.tail.prev = self.head
        self.map = {}
        self.size = 0

    def get(self, key: int) -> int:
        if key in self.map:
            node = self.map[key]
            self.__removeNode(node)
            self.__addTail(node)

            return node.val
        return -1

    def put(self, key: int, value: int) -> None:
        if self.get(key) != -1:
            self.map[key].val = value
            return
        if self.size + 1 > self.cap:
            headNode = self.head.next
            self.__removeNode(headNode)
            del self.map[headNode.key]
            self.size -= 1
        node = Node(key, value)
        self.__addTail(node)
        self.map[key] = node
        self.size += 1

    def __removeNode(self, node):
        prevNode = node.prev
        nextNode = node.next
        prevNode.next = nextNode
        nextNode.prev = prevNode

    def __addTail(self, node):
        tailNode = self.tail.prev
        tailNode.next = node
        node.prev = tailNode
        node.next = self.tail
        self.tail.prev = node
